package pers.whj.util.graph;

import pers.whj.util.NoSuchElementException;
import pers.whj.util.list.List;
import pers.whj.util.list.QueueList;
import pers.whj.util.list.SeqList;

public abstract class AbstractGraph<T> implements Graph<T>, GraphOp<T> {
    private static final int DEFAULT_MAX_VERTICES = 32;

    // if it is a directed graph
    protected final boolean mIsDirected;

    protected int mMaxVertices;
    protected int mNumVertices;
    protected long mNumEdges;

    public AbstractGraph() {
        this(DEFAULT_MAX_VERTICES, false);
    }

    public AbstractGraph(int maxVertices) {
        this(maxVertices, false);
    }

    public AbstractGraph(int maxVertices, boolean isDirected) {
        mMaxVertices = maxVertices > 0 ? maxVertices : DEFAULT_MAX_VERTICES;
        mNumVertices = 0;
        mNumEdges = 0;
        this.mIsDirected = isDirected;
    }

    @Override
    public boolean isDirected() {
        return mIsDirected;
    }

    @Override
    public boolean isEmpty() {
        return mNumEdges == 0;
    }

    @Override
    public boolean isFull() {
        return mNumVertices == mMaxVertices && isCompleteGraph();
    }

    @Override
    public int maxVertices() {
        return mMaxVertices;
    }

    @Override
    public int numOfVertices() {
        return mNumVertices;
    }

    @Override
    public long numOfEdges() {
        return mNumEdges;
    }

    @Override
    public int getPosition(T vertex) {
        for (int i = 0; i < mNumVertices; i++) {
            if (vertex(i).data == vertex) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public T getValue(int v) {
        checkIfVertexExists(v);
        return vertex(v).data;
    }

    @Override
    public void setValue(int v, T data) {
        checkIfVertexExists(v);
        vertex(v).data = data;
    }

    @Override
    public void setValue(T preData, T data) {
        setValue(getPosition(preData), data);
    }

    @Override
    public void traversal(Visit<T> visit, T data) {
        traversal(visit, getPosition(data));
    }

    @Override
    public void traversal(Visit<T> visit, int v) {
        checkIfVertexExists(v);
        boolean[] visited = new boolean[mNumVertices];
        DFS(visit, v, visited);
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                DFS(visit, i, visited);
            }
        }
    }

    @Override
    public void DFS(Visit<T> visit, T data) {
        DFS(visit, getPosition(data));
    }

    @Override
    public void DFS(Visit<T> visit, int v) {
        checkIfVertexExists(v);
        boolean[] visited = new boolean[mNumVertices];
        DFS(visit, v, visited);
    }

    @Override
    public void BFS(Visit<T> visit, T data) {
        BFS(visit, getPosition(data));
    }

    @Override
    public void BFS(Visit<T> visit, int v) {
        checkIfVertexExists(v);
        boolean[] visited = new boolean[mNumVertices];
        visited[v] = true;
        visit.visit(v, vertex(v).data);
        QueueList<Integer> queue = new QueueList<>();
        queue.offer(v);
        while (!queue.isEmpty()) {
            v = queue.poll();
            int w = getFirstNeighbor(v);
            while (w != -1) {
                if (!visited[w]) {
                    visited[w] = true;
                    visit.visit(w, vertex(w).data);
                    queue.offer(w);
                }
                w = getNextNeighbor(v, w);
            }
        }
    }

    @Override
    public List<List<Integer>> getComponents() {
        List<List<Integer>> result = new SeqList<>();
        if (mNumVertices > 0) {
            boolean[] visited = new boolean[mNumVertices];
            for (int i = 0; i < visited.length; i++) {
                if (!visited[i]) {
                    List<Integer> list = new SeqList<>();
                    BFS(i, visited, list);
                    result.insert(list);
                }
            }
        }
        return result;
    }

    @Override
    public int numOfComponents() {
        return getComponents().length();
    }

    @Override
    public boolean isConnectedGraph() {
        return getComponents().length() <= 1;
    }

    protected void checkIfVertexExists(int v) {
        if (v < 0 || v >= mNumVertices) {
            throw new NoSuchElementException("vertex doesn't exists, num of vertices: " + mNumVertices + ", vertex index: " + v);
        }
    }

    protected void checkIfVerticesExist(int v1, int v2) {
        if (v1 < 0 || v1 >= mNumVertices) {
            throw new NoSuchElementException("vertex doesn't exists, num of vertices: " + mNumVertices + ", vertex index: " + v1);
        }
        if (v2 < 0 || v2 >= mNumVertices) {
            throw new NoSuchElementException("vertex doesn't exists, num of vertices: " + mNumVertices + ", vertex index: " + v2);
        }
    }

    protected void DFS(Visit<T> visit, int v, boolean[] visited) {
        visit.visit(v, vertex(v).data);
        visited[v] = true;
        int w = getFirstNeighbor(v);
        while (w != -1) {
            if (!visited[w]) {
                DFS(visit, w, visited);
            }
            w = getNextNeighbor(v, w);
        }
    }

    protected void DFS(int v, boolean[] visited, List<Integer> list) {
        list.insert(v);
        visited[v] = true;
        int w = getFirstNeighbor(v);
        while (w != -1) {
            if (!visited[w]) {
                DFS(w, visited, list);
            }
            w = getNextNeighbor(v, w);
        }
    }

    protected void BFS(int v, boolean[] visited, List<Integer> list) {
        visited[v] = true;
        list.insert(v);
        QueueList<Integer> queue = new QueueList<>();
        queue.offer(v);
        while (!queue.isEmpty()) {
            v = queue.poll();
            int w = getFirstNeighbor(v);
            while (w != -1) {
                if (!visited[w]) {
                    visited[w] = true;
                    list.insert(w);
                    queue.offer(w);
                }
                w = getNextNeighbor(v, w);
            }
        }
    }

    protected abstract Vertex<T> vertex(int index);

    protected static class Vertex<T> {
        protected T data;

        public Vertex(T data) {
            this.data = data;
        }
    }
}